#include <iostream>
#include <windows.h>

using namespace std;

// 定义环形节点
struct YsfNode {
    int number;
    YsfNode *next;
};

// 初始化指定节点的约瑟夫环
YsfNode *InitYsfNode(int n) {
    YsfNode *head = new YsfNode;
    //易错点：
    // head 头元素必须要单独创建，不能放在for循环，避免head节点跟着游标节点的指针一起跑
    head->next = nullptr;
    head->number = 1;
    YsfNode *cursorNode = head;

    for (int i = 2; i <= n; i++) {
        YsfNode *temp = new YsfNode();
        temp->number = i;
        temp->next = nullptr;

        cursorNode->next = temp;
        cursorNode = temp;
    }
    // 约瑟夫环形，必须将最后一个元素的指针指向head，这样才能形成环形
    cursorNode->next = head;
    return head;
}


// 根据规则不断拆除节点，计算出最后剩余的节点即可
int calcLastOneEle(YsfNode *head, int startNum, int step) {
    YsfNode *preNode = nullptr;
    YsfNode *cursorNode = head;

    // 寻找起步元素对应的指针
    while (cursorNode->next != cursorNode) {
        if (cursorNode->number == startNum) {
            //    cout << "find start ele：" << startNum << "  rela ptr：" << cursorNode << endl;
            break;
        }
        cursorNode = cursorNode->next;
    }

    // 继续通过循环 + 步长(step) 计算拆除的元素
    while (cursorNode->next != cursorNode) {
        //  注意 ：  i <step ，就是step的起始元素包括开始元素本身，
        //  如果 i<= step  ，说明从开始元素的下一个元素算 step 的个数
        for (int i = 1; i < step; i++) {
            preNode = cursorNode;
            cursorNode = cursorNode->next;
        }
        // 拆环，通过指针的重新指向修改环形队列元素
        preNode->next = cursorNode->next;
        delete cursorNode;  // 释放被弹出元素对应的内存空间
        // 被删除的前一个元素的 next 重新指向下一个节点
        cursorNode = preNode->next;

    }

    // 返回最后剩余的漏网之鱼就是胜利者
    return cursorNode->number;
}
int main() {

    DWORD startSec = GetTickCount();

    int num = 1000000;  // 100 万节点
    int lastOneNum = -1;   //
    for (int i = 0; i < 10; i++) {
        YsfNode *head = InitYsfNode(num);
        lastOneNum = calcLastOneEle(head, 3, 2);
    }

    //  根据网友反馈： 在循环中间做输出，输出命令本身可能会影响性能，所以最后只输出一次
    cout << "lastOne:" << lastOneNum << endl;

    cout << "单次平均耗时(ms)： " << (GetTickCount() - startSec) / 10 << endl;
    return 0;

}